/**
 * 
 */
package dp.passed;

/**
 * @author xyyi
 *
 */
public class MaximumSubsequentProduct {

	/**
	 * http://uva.onlinejudge.org/external/110/11059.html
	Problem D - Maximum Product
	Time Limit: 1 second

	Given a sequence of integers S = {S1, S2, ..., Sn}, you should determine what is the value of the maximum positive product involving consecutive terms of S. If you cannot find a positive sequence, you should consider 0 as the value of the maximum product.
	Input

	Each test case starts with 1 ≤ N ≤ 18, the number of elements in a sequence. Each element Si is an integer such that -10 ≤ Si ≤ 10. Next line will have N integers, representing the value of each element in the sequence. There is a blank line after each test case. The input is terminated by end of file (EOF).
	Output

	For each test case you must print the message: Case #M: The maximum product is P., where M is the number of the test case, starting from 1, and P is the value of the maximum product. After each test case you must print a blank line.
	Sample Input

	3
	2 4 -3

	5
	2 5 -1 2 -1

	Sample Output

	Case #1: The maximum product is 8.

	Case #2: The maximum product is 20.
	
	Solution:
	http://www.youtube.com/watch?v=twaGE43dbu0
	
	globalLargetPositive = 0
	
	1 Initial state or : 
	currentLargestPositive = -1, currentLargestNegative = 1
	2 if a positive value with k
	currentLargestPositive = currentLargestPositive * k
	currentLargestNegative = currentLargestNegative * k
	  if a negative value with k
	  currentLargestPositive = currentLargestNegative * k
	  currentLargestNegative = currentLargestPositive * k
	  if a value with 0
	  currentLargestPositive = -1
	  currentLargestNegative = 1
	3 update globalLargetPositive
		if (currentLargestPositive > globalLargetPositive)
			globalLargetPositive = currentLargestPositive
	4 if currentLargestPositive < 1
		currentLargestPositive = -1
	
	 */
	public double maxSubsequentProduct(double[] numbers) {
		assert (numbers != null && numbers.length > 0);

		double maxPositive = 0;
		double currPositive = -1;
		double currNegative = 1;
		for (double number : numbers) {
			if (number > 0) {
				currPositive = currPositive == -1 ? number : currPositive
						* number;
				currNegative = currNegative == 1 ? currNegative : currNegative
						* number;
			} else if (number < 0) {
				if (currNegative == 1) {
					currNegative = currPositive == -1 ? number : currPositive
							* number;
					currPositive = -1;
				} else {
					double tempPositive = currPositive;
					currPositive = currNegative * number;
					currNegative = tempPositive == -1 ? number : tempPositive
							* number;
				}
			} else { // number == 0
				currPositive = -1;
				currNegative = 1;
			}

			maxPositive = currPositive > maxPositive ? currPositive
					: maxPositive;

			currPositive = currPositive < 1 ? -1 : currPositive;
		}

		return maxPositive;
	}

	//	public int maxProduct(int[] n) {
	//		
	//	}

	/**
	 * 
	 */
	public MaximumSubsequentProduct() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MaximumSubsequentProduct msp = new MaximumSubsequentProduct();
		double[][] numsArr = { { 0.5, -2.5, 3.0, -6 }, { -2 },
				{ -0.6, 0.6, -0.7, 0.8, 0.5 }, { -0.5, -0.7, -0.6 },
				{ 2, 5, -1, 2, -1 } };
		for (double[] numbers : numsArr) {
			for (double number : numbers) {
				System.out.printf("%f,", number);
			}
			System.out.printf(" max subsequent product is %f\n",
					msp.maxSubsequentProduct(numbers));
		}

	}
}
